package com.xk._03真题骗._06二叉树;

import com.xk._03真题骗._00bean.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.cn/problems/recover-binary-search-tree/
 * @description:
 * @author: xu
 * @date: 2022/11/5 20:43
 */
public class _99恢复二叉搜索树 {
    /*
    * 思路：中序遍历 -- 非递归
    * 时间复杂度：O(n)
    * 空间复杂度：O(n)
    * */
    public void recoverTree1(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> stack = new LinkedList<>();
        List<TreeNode> list = new ArrayList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode pop = stack.pop();
                list.add(pop);
                node = pop.right;
            }
        }
        TreeNode first = null, second = null;
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i-1).val > list.get(i).val) {
                second = list.get(i);
                if (first != null) break;
                first = list.get(i-1);
            }
        }
        // 交换2个交换结点的值
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }


    /*==========================================================================*/
    // 上一次中序遍历过的节点
    private TreeNode prev;
    // 第一个错误节点
    private TreeNode first;
    // 第二个错误节点
    private TreeNode second;
    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param root 是一颗错误的二叉搜索树（有2个节点被错误交换）
     */
    public void recoverTree2(TreeNode root) {
        findWrongNodes(root);
        // 交换2个交换结点的值
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    private void findWrongNodes(TreeNode root) {
        if (root == null) return;
        findWrongNodes(root.left);
        // 出现了逆序对
        if (prev != null && prev.val > root.val) {
            // 第二个错误节点：最后一个逆序对中较小的那个节点
            second = root;
            // 第一个错误节点：第一个逆序对中较大的那个节点
            if (first != null) return;
            first = prev;
        }
        prev = root;
        findWrongNodes(root.right);
    }

    /*==================================二叉树的Morris遍历========================================*/
    /**
     * 二叉树的Morris遍历
     * @param root
     */
    public void recoverTree(TreeNode root) {
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                // node左节点不为空
                // 找到node的前驱节点，即node左子节点的最右下方
                TreeNode pred = node.left;
                while (pred.right != null && pred.right != node) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = node;
                    node = node.left;
                } else {
                    find(node);
                    pred.right = null;
                    node = node.right;
                }
            } else {
                find(node);
                node = node.right;
            }
        }
        // 交换2个交换结点的值
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

    private void find(TreeNode node) {
        // 出现了逆序对
        if (prev != null && prev.val > node.val) {
            // 第二个错误节点：最后一个逆序对中较小的那个节点
            second = node;
            // 第一个错误节点：第一个逆序对中较大的那个节点
            if (first != null) return;
            first = prev;
        }
        prev = node;
    }
}
